Sorting
Sorting is one of those things that shows up in almost every other problem without being the point of the problem. You sort a list of intervals before merging them, sort a dictionary by value to find the top result, sort a list of tuples by some field, and so on. Python gives you two ways to do it, plus a key= argument that handles almost every variation you will run into.
sort() vs sorted(): in place or a new list
O(n log n)sorted() takes any iterable and returns a new sorted list. The original is untouched:
list.sort() is a method on lists that sorts in place and returns None:
Note
THE gotcha: because sort() returns None, writing numbers = numbers.sort() throws away your list. numbers is now None, not a sorted list:
If you want to keep using the variable name, just call numbers.sort() on its own line. If you want a new list and want to keep the original around too, use sorted() instead.
Sorting with key=
O(n log n)key= takes a function and applies it to every element before comparing them. The list itself doesn't change, only the order it comes out in. Sort by string length:
Sort case-insensitively, so "bob" and "Alice" mix properly:
Sort a list of numbers by absolute value:
Note
Add reverse=True to any of these calls to sort largest first without changing the key function. Writing a key that negates the value works too, but only for numbers, and it's easy to get wrong, so reverse=True is the better default.
How do I sort a list of tuples by the second element?
A lambda that pulls out the field you care about is the most common way to write this:
operator.itemgetter does the same job without a lambda, and reads a little clearer once you're used to it:
Both give the same result. Use whichever one you'd reach for faster under interview pressure; a lambda is the safer default if you're not sure you'll remember the import.
How do I sort a dictionary by its values?
Dicts don't have a .sort() method, so sort the .items() view instead. That gives you a list of (key, value) tuples, which you can key on the value:
Note
Feeding that sorted list of tuples back into dict() works because Python 3.7+ dicts remember insertion order. The resulting dict prints in the order you just sorted into, so this round trip is a quick way to get a "dict sorted by value" without a separate library.
Sorting objects by attribute
Same idea as tuples, but pulling an attribute off an object instead of an index:
operator.attrgetter is the attribute version of itemgetter, and it's especially handy once you're sorting by more than one attribute at a time:
Sorting by multiple keys
Give key= a tuple and Python compares tuples element by element, so this sorts by age first and breaks ties by name:
Note
Why this works: Python's sort is stable, meaning elements that compare equal keep their original relative order. That's what makes sorting by the least significant key first, then the most significant key, produce the exact same result as a tuple key:
A tuple key is usually the more direct way to write it, but the successive-sort trick matters once the keys get complicated, or you need to combine sort orders that were built separately.
Why do I get TypeError when sorting?
Python 3 compares elements with < while sorting, and it has no idea how to compare an int to a str, so mixed types blow up:
Note
Python 2 let you pass a cmp= function that could compare anything to anything, however oddly. Python 3 removed cmp= entirely, in favor of key=. If your data genuinely mixes types, normalize them with a key function first, like key=str, instead of trying to compare the raw values.
Where sorting shows up in interviews
Sorting is rarely the whole problem, but it's often step one. The biggest pattern to know is intervals: almost every interval problem starts by sorting the intervals, usually by start time, before doing anything else.
- Intervals covers why sorting first turns a messy interval problem into a single pass over an already-ordered list.
- Merge Intervals sorts by start time, then walks the list once, merging any interval that overlaps the one before it.
- Meeting Rooms II sorts start and end times separately to figure out how many rooms are in use at once.
- Non-overlapping Intervals sorts by end time instead of start time, which is the detail that trips people up the first time they see it.